package com.jiang.daily.Q3346;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/10/21 20:14
 */
class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);

        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        int lastIndex = 0;
        int res = 0;

        for (int i = 1; i < len; i++) {
            if (nums[i] != nums[lastIndex]) {
                map.put(nums[lastIndex], i - lastIndex);
                res = Math.max(res, i - lastIndex);
                lastIndex = i;
            }
        }

        map.put(nums[lastIndex], len - lastIndex);
        res = Math.max(res, len - lastIndex);

        for (int v = nums[0]; v <= nums[len - 1]; v++) {
            int l = leftRound(nums, v - k); // 第一个大于等于 v - k 的下标
            int r = rightRound(nums, v + k); // 从右往左，第一个小于等于 v + k 的下标
            int tempMax = 0;
            if (map.containsKey(v)) {
                tempMax = Math.min(r - l + 1, numOperations + map.get(v));
            } else {
                tempMax = Math.min(r - l + 1, numOperations);
            }
            res = Math.max(res, tempMax);
        }

        return res;
    }

    // private int leftRound(int[] nums, int value) {
    //     int l = 0, r = nums.length - 1;

    //     while (l <= r) {
    //         int mid = (l + r) / 2;
    //         if (nums[mid] < value) {
    //             l = mid + 1;
    //         } else {
    //             r = mid - 1;
    //         }
    //     }
    //     return l;
    // }

    // private int rightRound(int[] nums, int value) {
    //     int l = 0, r = nums.length - 1;

    //     while (l <= r) {
    //         int mid = (l + r) / 2;
    //         if (nums[mid] > value) {
    //             r = mid - 1;
    //         } else {
    //             l = mid + 1;
    //         }
    //     }
    //     return l - 1;
    // }

    private int leftRound(int[] nums, int value) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int rightRound(int[] nums, int value) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] > value) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}
